public class solution_1328_BreakPalindrome {
    // 2025年3月5日
    public static String breakPalindrome(String palinderome) {
        if (palinderome.length() <= 1) {
            // 小于2个字符的不存在替换一个字符变为非回文序列
            return "";
        }
        // 回文字符串长度>2
        // 构成满足字典序最小的非回文序列
        // 第一个可能性 将第一个不是a的字符替换为a
        // 第二个可能性 全为 a 将最后一个替换为b
        // 第三个可能性 全部不为a 将第一个替换为a

        int minDistance = Integer.MAX_VALUE;
        int temp = 0;
        // 下标初始化为最后一个字符的位置
        int index = palinderome.length() - 1;
        char[] chars = palinderome.toCharArray();
        // 获取回文字符串中 第一个不为 a 的位置 index, 回文序列只需要遍历一半的字符串
        for (int i = 0; i < chars.length / 2; i++) {
            temp = (int) chars[i] - 'a';
            if (temp > 0) {
                minDistance = Math.min(minDistance, temp);
                // minDistance 更新时下标才更新
                index = minDistance == temp ? i : index;
                break;
            }
        }

        // 可能性2 字符串 全为a
        if (minDistance == Integer.MAX_VALUE && index == palinderome.length() - 1) {
            chars[index] = 'b';
            return new String(chars);
        }
        // 第一和第三种情况合并处理
        chars[index] = 'a';
        return new String(chars);
    }

    public static void main(String[] args) {
        System.out.println(breakPalindrome("aa"));
        System.out.println(breakPalindrome("abacaba"));
        System.out.println(breakPalindrome("bbbbbb"));
    }
}